package zuo.test3;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: Forx
 * @Data: 2021/6/13
 * @Desc: Algorithm - zuo.test3
 * @Version: v1.0
 */
public class Main {
    public static void swap(int[] in,int a ,int b){
        in[a]^=in[b];
        in[b]^=in[a];
        in[a]^=in[b];
    }
    public static void main(String[] args) {
        int[] buff1 = {3,4,1,43,5,23,5,3,5,7,78};
        heapSort(buff1);
        System.out.println(Arrays.toString(buff1));

    }
    public static void heapInsert(int[] in,int index){
        while ( index > 0 && in[index] > in[(index-1)>>1]){
            swap(in,index,(index-1)>>1);
            index = (index-1)>>1;
        }
    }
    public static void heapIfy(int[] in,int index,int heapSize){
        int leftSon = index*2+1;
        while (leftSon < heapSize){
            int larger = (leftSon+1 < heapSize) && (in[leftSon] < in[leftSon+1]) ? leftSon+1:leftSon;
            larger = in[larger]>in[index]?larger:index;
            if(larger==index)break;
            swap(in,index,larger);
            index = larger;
            leftSon = index*2+1;
        }
    }
    public static void heapSort(int[] in){
        int heapSize = 1;
        while (heapSize < in.length){//O(N)
            heapInsert(in,heapSize);//O(logN)
            heapSize++;
        }
        while (heapSize > 0){
            swap(in,0,--heapSize);
            heapIfy(in,0,heapSize);
        }
    }
    public static void heapSort2(int[] in){
        int heapSize = 1;
        for (int i = in.length-1; i >0; i--) {
            heapIfy(in,i,in.length);
        }
        while (heapSize > 0){
            swap(in,0,--heapSize);
            heapIfy(in,0,heapSize);
        }
    }

    /**
     * 堆排序扩展题目
     * 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元
     * 素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的
     * 排序算法针对这个数据进行排序。
     * 我们可以利用小根堆,先将0-k+1进行小根堆排序,然后输出arr[0] 后
     * swap(arr[0],arr[k+2]),然后调整小根堆后输出arr[0]
     * 在java中的PriorityQueue默认使用的就是小根堆
     * 故我们可以利用这个
     * */
    public static void sortArrayDistanceLessK(int[] in,int k){
        PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
        int index = 0;
        for (; index <= Math.min(k, in.length); index++) {
            smallHeap.add(in[index]);
        }
        int i = 0;
        for (; index < in.length; i++,index++) {
                smallHeap.add(in[index]);
                in[i] = smallHeap.poll();
        }
        while (!smallHeap.isEmpty()){
            in[i++] = smallHeap.poll();
        }
    }
    /**
     * java中的比较器返回正数交换,负数不动,0 无所谓
     * 因此从小-大 需要 return first-second
     * */
    public  static void biggerHeap(){
        PriorityQueue<Integer> biggerHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;//正数在上面,负数在下面,0无所谓
            }
        });//初始化一个大根堆
    }

    /**
     * bucketSort
     * 计数排序 - 假定我们知道数据的分布范围,如0-100;则我们遍历数组统计每个数的频率
     *           如0有7个...,则在辅助数组上的0位置赋值7,最后根据辅助数组还原整个数组
     *           此时排序的效率是O(N),空间效率未知,因为要根据数据的分布情况来计算
     * 基数排序 - 课本上有,并且就是桶排序
     *
     * */
    public static void radixSort(int[] in){
        if(in==null || in.length == 1)return;

    }
    /**
     * @brief return how how many bits that the biggest num in the inputArray have
     * */
    public static int maxNumBits(int[] in){
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < in.length; i++) {
            if(max < in[i])max = in[i];
        }
        int res = 0;
        while (max!=0){
            res++;
            max/=10;
        }
        return res;
    }
    /**
     * @param in  inputArray
     * @param left minIndex
     * @param right maxIndex
     * @param digits how many bits that the biggest num in the inputArray have
     * in:      [13,21,11,52,62]
     * count:   [0,2,2,1,0,...]  : 统计各个个位的频率
     * count:   [0,2,4,5,5,...]  :  统计个位是这个的数有几个小于等于它的
     * bucket:  [21,11,52,62,13] :  放到桶中,这里面必须从右往左放,因为上面统计的是小于等于的,右边是属于大于它的
     * in:      [21,11,52,62,13]
     *
     * in:      [21,11,52,62,13]
     * count:   [0,2,1,1,0,1,1...]
     * count:   [0,2,3,4,4,5,6,6...]
     * bucket:  [11,13,21,52,62]
     * in:      [11,13,21,52,62]
     *
     * */
    public static void radixSort(int[] in, int left,int right,int digits){
        final int radix = 10;
        int i = 0,j = 0;
        int[] bucket = new int[right - left +1];
        for (int k = 1; k < digits; k++) {
            int[] count = new int[radix];
            for (int l = left; l <= right; l++) {
                count[getDigit(in[l],k)]++;
            }
            for (int l = 1; l < radix; l++) {
                count[l] += count[l-1];
            }
            for (int l = right; l >=left; l--) {
                j = getDigit(in[l],k);
                bucket[count[j] - 1] = in[l];
                count[j]--;
            }
            j = 0;
            for (int l = left; l <= right ; l++,j++) {
                in[l] = bucket[j];
            }
        }
    }
    /**
     * @param num input num
     * @param d which bit want to get
     * */
    public static int getDigit(int num,int d){
        return ((num/(int)Math.pow(10,d-1)))%10;
    }
    /**
     *          总结
     *          时   空   稳
     * 选择     n^2   1   F
     * 冒泡     n^2   1   T
     * 插入     n^2   1   T
     * 归并    NlogN  n   T
     * 快排    NlogN logN F
     * 堆     NlogN  1    F
     *
     * q1:为什么基础类型的排序大多用快排
     *      自定义类型用归并
     * a1:基础类型没必要保存稳定
     *
     *
     * */

}


